Bose-Chaudhuri-Hocquenghem (BCH) code is one of the most widely used error correction code (ECC) techniques in the storage and communication devices. BCH code can detect and correct random errors occurred due to channel noises and defects within memory devices. The encoding procedures of BCH codeword can be implemented by linear feedback shift register (LFSR) and some combination logics together. A conventional linear feedback shift register circuit is shown in FIG. 1. In order to speed up operation, the circuit is often designed to be parallelization. It can calculate several inputted bit datum at the same time. The alphabet p in FIG. 1 represents the p-bit datum of the inputted R′(j) in the jth clock cycle for synchronized calculation. After encoding, the results of Z(j) are outputted. If the code length is n bits, the procedures of encoding will complete after [n/p] clock cycles.
A detailed illustration about BCH encoding is provided below. For an encoded BCH codeword having n bits, it includes a k-bit message. During encoding processes, a generating polynomial below is applied:g(x)=xR+g′R-1xR-1+g′R-2xR-2+ . . . +g′2x2+g′1x1+g′0,where R=n−k+1. When an encoder capable of processing encoding of p parallel computations synchronously is used, for a n-bit initial processing data including the k-bit message and being divided per p bits as R′(1), R′(2), . . . R′(n/p) (R′(n/p) is not necessary p bits), and inputted to the encoder per clock cycle sequentially for operation. In view of a general formula, in a jth clock cycle (1≦j≦n/p), the outputted computed values are as: Z(j)=Fp×[Z(j−1)+R′(j)]. It should be noticed that all elements in Z(0) are 0. In order to facilitate operation, it is denoted thatR′(j)=[r′0(j)r′1(j)r′2(j) . . . r′p-1(j)|0 . . . 0]1×RT.R′(j) is the jth p bits. Z(j) has R bits denoting by Z0(j), Z1(j), . . . ZR-1(j), respectively. Other expressions in the above formula are further described as below:
            F      p        =          [                                    F                          p              -              1                                ×                      [                                                                                g                                          R                      -                      1                                        ′                                                                                                                    g                                          R                      -                      2                                        ′                                                                                                ⋮                                                                                                  g                    1                    ′                                                                                                                    g                    0                    ′                                                                        ]                          |                                  ⁢                              first            ⁢                                                  ⁢            R                    -                      1            ⁢                                                  ⁢            columns            ⁢                                                  ⁢            of            ⁢                                                  ⁢                          F                              p                -                1                                                        ]                  F      1        =          [                                                  g                              R                -                1                            ′                                            1                                0                                …                                0                                                              g                              R                -                2                            ′                                            0                                1                                …                                0                                                ⋮                                ⋮                                ⋮                                ⋮                                ⋮                                                              g              1              ′                                            0                                0                                …                                1                                                              g              0              ′                                            0                                0                                …                                0                              ]      Let F′=[first p columns of Fp|Fp], transpose of Z(j) can be obtained.
                                          Z            ⁡                          (              j              )                                T                =                ⁢                              {                                          F                p                            ×                              [                                                      Z                    ⁡                                          (                                              j                        -                        1                                            )                                                        +                                                            R                      ′                                        ⁡                                          (                      j                      )                                                                      ]                                      }                    T                                        =                ⁢                                            [                                                Z                  ⁡                                      (                                          j                      -                      1                                        )                                                  +                                                      R                    ′                                    ⁡                                      (                    j                    )                                                              ]                        T                    ×                      F                          p              T                                                              =                ⁢                              [                                                            R                  ′                                ⁡                                  (                  j                  )                                            ⁢                              Z                ⁡                                  (                                      j                    -                    1                                    )                                                      ]                    ×                      F                          ′              T                                          
A circuit fulfills this operation can also achieve the encoding operation shown in FIG. 1. An encoded codeword is obtained in [n/p] clock cycles
The pervious method can only be used for a fixed code rate and code length in the same GF(2m). For some applications, various code lengths, code rates, number of m in the GF(2m), and the values of the parallel parameter p may be required. Conventionally, those requirements can be implemented with specified BCH encoders. Thus, the hardware complexity will increase. To reduce the hardware complexity, some designers may insert a lot of multiplexers into the LFSR to share registers. However, the additional area and delay time due to those multiplexer insertions will harm the benefit.
Hence, a proposed method used to share one LFSR for various BCH codes and associated encoder is desired. Moreover, the method can enlarge searching space of common sub-expressions (CSEs) in one matrix to reduce the hardware logic area.